import numpy as np

import sys

values = [[], []]
paretoRate = 0


# print(values)
# sys.exit(999)
def fast_non_dominated_sort(values, pop_size):
    """
    快速非支配排序
    :param values: 解集【目标函数1解集，目标函数2解集...】
    :return:返回解的各层分布集合序号。类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]] 其中[1]表示Pareto 最优解对应的序号
    """
    values11 = values[0]  # 函数1解集
    S = [[] for i in range(0, len(values11))]  # 存放 每个个体支配解的集合。
    front = [[]]  # 存放群体的级别集合，一个级别对应一个[]
    n = [0 for i in range(0, len(values11))]  # 每个个体被支配解的个数 。即针对每个解，存放有多少好于这个解的个数
    rank = [np.inf for i in range(0, len(values11))]  # 存放每个个体的级别

    for p in range(0, len(values11)):  # 遍历每一个个体
        # ====得到各个个体 的被支配解个数 和支配解集合====
        S[p] = []  # 该个体支配解的集合 。即存放差于该解的解
        n[p] = 0  # 该个体被支配的解的个数初始化为0  即找到有多少好于该解的 解的个数
        for q in range(0, len(values11)):  # 遍历每一个个体
            less = 0  # 的目标函数值小于p个体的目标函数值数目
            equal = 0  # 的目标函数值等于p个体的目标函数值数目
            greater = 0  # 的目标函数值大于p个体的目标函数值数目
            for k in range(len(values)):  # 遍历每一个目标函数
                if values[k][p] > values[k][q]:  # 目标函数k时，q个体值 小于p个体
                    less = less + 1  # q比p 好
                if values[k][p] == values[k][q]:  # 目标函数k时，p个体值 等于于q个体
                    equal = equal + 1
                if values[k][p] < values[k][q]:  # 目标函数k时，q个体值 大于p个体
                    greater = greater + 1  # q比p 差

            if (less + equal == len(values)) and (equal != len(values)):
                n[p] = n[p] + 1  # q比p,  比p好的个体个数加1

            elif (greater + equal == len(values)) and (equal != len(values)):
                S[p].append(q)  # q比p差，存放比p差的个体解序号

        # =====找出Pareto 最优解，即n[p]===0 的 个体p序号。=====
        if n[p] == 0:
            rank[p] = 0  # 序号为p的个体，等级为0即最优
            if p not in front[0]:
                # 如果p不在第0层中
                # 将其追加到第0层中
                front[0].append(p)  # 存放Pareto 最优解序号

    # =======划分各层解========

    i = 0
    while front[i] != []:  # 如果分层集合为不为空
        Q = []
        for p in front[i]:  # 遍历当前分层集合的各个个体p
            for q in S[p]:  # 遍历p 个体 的每个支配解q
                n[q] = n[q] - 1  # 则将fk中所有给对应的个体np-1
                if n[q] == 0:
                    # 如果nq==0
                    rank[q] = i + 1
                    if q not in Q:
                        Q.append(q)  # 存放front=i+1 的个体序号

        i = i + 1  # front 等级+1
        front.append(Q)

    del front[len(front) - 1]  # 删除循环退出 时 i+1产生的[]

    return front  # 返回各层 的解序号集合 # 类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]]


def crowding_distance(values, front, pop_size):
    """
    拥挤距离
    :param values: 群体[目标函数值1，目标函数值2,...]
    :param front: 群体解的等级，类似[[1], [9], [0, 8], [7, 6], [3, 5], [2, 4]]
    :return: front 对应的 拥挤距离
    """
    distance = np.zeros(shape=(pop_size,))  # 拥挤距离初始化为0
    for rank in front:  # 遍历每一层Pareto 解 rank为当前等级
        for i in range(len(values)):  # 遍历每一层函数值（先遍历群体函数值1，再遍历群体函数值2...）
            valuesi = [values[i][A] for A in rank]  # 取出rank等级 对应的  目标函数值i 集合
            rank_valuesi = zip(rank, valuesi)  # 将rank,群体函数值i集合在一起
            sort_rank_valuesi = sorted(rank_valuesi, key=lambda x: (x[1], x[0]), reverse=True)  # 先按函数值大小排序，再按序号大小排序

            sort_ranki = [j[0] for j in sort_rank_valuesi]  # 排序后当前等级rank
            sort_valuesi = [j[1] for j in sort_rank_valuesi]  # 排序后当前等级对应的 群体函数值i
            # print(sort_ranki[0],sort_ranki[-1])
            distance[sort_ranki[0]] = np.inf  # rank 等级 中 的最优解 距离为inf
            distance[sort_ranki[-1]] = -np.inf  # rank 等级 中 的最差解 距离为inf

            # 计算rank等级中，除去最优解、最差解外。其余解的拥挤距离
            for j in range(1, len(rank) - 2):
                # print(sort_valuesi[j + 1])
                # print("****")
                if max(sort_valuesi) - min(sort_valuesi) != 0:
                    distance[sort_ranki[j]] = distance[sort_ranki[j]] + (sort_valuesi[j + 1] - sort_valuesi[j - 1]) / (
                            max(sort_valuesi) - min(sort_valuesi))  # 计算距离
                else:
                    distance[sort_ranki[j]] = np.inf
    # 按照格式存放distances
    distanceA = [[] for i in range(len(front))]  #
    for j in range(len(front)):  # 遍历每一层Pareto 解 rank为当前等级
        for i in range(len(front[j])):  # 遍历给rank 等级中每个解的序号
            distanceA[j].append(distance[front[j][i]])

    return distanceA


def decorate(pop):
    """

    :param pop: 中间种群
    :return: 基于偏序关系的中间种群
    """
    values1 = []
    values2 = []
    pop_size = len(pop)
    # print(pop_size)  # 亲子两代的中间种群
    for indiv in pop:
        values1.append(indiv.CP)
        values2.append(indiv.CO)
    values = [values1, values2]
    # print("----------------")
    # print(values1)
    # print(values2)
    return values, pop_size


# NSGA2
def NSGA2(pop):
    values, pop_size = decorate(pop)
    front = fast_non_dominated_sort(values, pop_size)
    distanceA = crowding_distance(values, front, pop_size)
    values1 = values[0]
    values2 = values[1]
    new_pop = []
    new_pop_length = 0
    stop = False  # （已失效）新种群规模限制标志
    for i in range(len(front)):
        # 每层按拥挤距离由大到小排序
        union = zip(front[i], distanceA[i])
        sorted_union = sorted(union, key=lambda x: x[1], reverse=True)
        result = zip(*sorted_union)
        front[i], distanceA[i] = [list(x) for x in result]
        # print("*******************")
        # print('当前等级 解的序号为:', front[i])
        for k in range(0, len(front[i])):
            # print(values1[front[i][k]], end="          ")
            # print(values2[front[i][k]])
            # print(pop[front[i][k]].cost)
            new_pop.append(pop[front[i][k]])
            new_pop_length += 1
            if new_pop_length == pop_size:  # 此判断无效 种群规模限制
                stop = True
                break
        # print('当前等级 解的拥挤距离为:', distanceA[i])
        if stop:
            break
    # print(len(new_pop))
    paretoNum = len(front[0])
    paretoRate = len(front[0]) / len(new_pop)
    # print("=============================================")
    # print(paretoRate)
    return new_pop, paretoRate, paretoNum


if __name__ == '__main__':
    values = [
        [1, 5, 5, 3, 4],
        [2, 1, 6, 4, 3]
    ]
    front = fast_non_dominated_sort(values, 5)
    distanceA = crowding_distance(values, front, 5)
    for i in range(len(front)):
        print('当前等级 解的序号为:', front[i])
        print('当前等级 解的拥挤距离为:', distanceA[i])
